package cn.edu.xjtu.work.tribonacci;

/**
 * 1137. 第 N 个泰波那契数
 * 
 * 泰波那契序列 Tn 定义如下： 
 * 
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 * 
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 */
public class Solution {
  /**
   * 动态规划
   * 
   * @param n
   * @return
   */
  public int tribonacci(int n) {
    if (n == 0) {
      return 0;
    }
    int p = 0;
    int q = 1;
    int r = 1;
    int count = 2;
    while (n > count) {
      int temp = r;
      r = p + q + r;
      p = q;
      q = temp;
      count++;
    }
    return r;
  }
}
